Game Theory

02/06/2024

• Game theory studies strategic interactions

• and multiperson decision theory

Defination - Normal form game

A normal form game consists of three things:

• A set of $N$$N$ players.

• A set of actions $A_i$$A_i$ for each $i\in N$$i \in N$ with element of $a_i\in A_i$$a_i\in A_i$

  And the action profiles: $A=A_1\times A_2\times \cdots \times A_N$$A = A_1\times A_2 \times \dots \times A_N$

• Payoffs. $u_i:A\to \mathbb{R}$$u_i : A \rightarrow \R$, $\mathrm{\forall }i\in N$$\forall i \in N$.

Example

A game of $N-2$$N-2$, $A_1=\{a_1,a_2\}$$A_1 = \{a_1,a_2\}$, and $A_2=\{b_1,b_2\}$$A_2 = \{b_1,b_2\}$

	$b_1$$b_1$	$b_2$$b_2$
$a_1$$a_1$	7,3	3,5
$a_2$$a_2$	5,5	7,2

The payoff here is (player 1, player 2)

Defination (strictly) dominate

Action $a\in A_1$$a \in A_1$ (strictly) dominates action $a^{\prime }\in A_1$$a^\prime \in A_1$ if $u_1(a,b)>u_1(a^{\prime },b)$$u_1(a,b) > u_1(a^\prime,b)$ for all $b\in A_2$$b\in A_2$

对所有的player 2 选择的strategy，player 1选择 $a$$a$ 都要比 选择 $a^{\prime }$$a^\prime$ 的收益(严格)更好

Definate weakly dominate

Action $a\in A_1$$a \in A_1$ weakly dominates action $a^{\prime }\in A_1$$a^\prime \in A_1$ if

• $u_1(a,b)\ge u_1(a^{\prime },b)$$u_1(a,b) \geq u_1(a^\prime,b)$ for all $b\in A_2$$b\in A_2$ ,

• $u_1(a,b)>u_1(a^{\prime },b)$$u_1(a,b) > u_1(a^\prime,b)$ for some $b\in A_2$$b\in A_2$ ,

In summary, strictly domination implies weak domination, and any two actions cannot weakly dominate each other.

And we have some descriptions:

Action $a\in A_1$$a \in A_1$ is "undominated" if it is not weakly dominated by any other $a^{\prime }\in A_1$$a^\prime \in A_1$.

Action $a\in A_1$$a \in A_1$ is "dominant" if it strictly dominates all other $a^{\prime }\in A_1$$a^\prime \in A_1$.

Action $a\in A_1$$a\in A_1$ is "weakly dominant " if it weakly dominates all other $a^{\prime }\in A_1$$a^\prime \in A_1$.

Action $a\in A_1$$a \in A_1$ is "dominated" if there exists another action $a^{\prime }\in A_1$$a^\prime \in A_1$ such that $a^{\prime }$$a^\prime$ dominates $a$$a$.

Then,

A rational player will never chooses a dominated action, and will always chooses a dominant action.

Example

if we do not know the payoffs for player 2, then we have no dominant and dominated actions so far.

Defination - Beliefs

Let ${\sigma }_2\in \mathrm{\Delta }(A_2)$$\sigma_2 \in \Delta(A_2)$ denotes player 1's beliefs about player 2's actions.

The expected utility $u_1(a,{\sigma }_2)$$u_1(a,\sigma_2)$ of action $a$$a$ is $\sum _{a_2\in A_2}{\sigma }_2(a_2)u_1(a,a_2)$$\sum_{a_2 \in A_2} \sigma_2(a_2) u_1(a,a_2)$.

Given ${\sigma }_2$$\sigma_2$, a rational player maximizes expected utility.

Since the set of actions are finite, there is always at least one best action.

Defination - Best response

Action $a\in A_1$$a\in A_1$ is a weak best response to beliefs ${\sigma }_2$$\sigma_2$ if $u_1(a,{\sigma }_2)\ge u_1(a^{\prime },{\sigma }_2)$$u_1(a,\sigma_2) \geq u_1(a^\prime , \sigma_2)$ for every action $a^{\prime }\in A_1$$a^\prime \in A_1$.

Defination - Never a best response

If $\mathrm{\forall }{\sigma }_2\in \mathrm{\Delta }(A_2)$$\forall \sigma_2 \in \Delta(A_2)$, action $a\notin BR({\sigma }_2)$$a \not \in BR(\sigma_2)$, then $a$$a$ is never (weak) best response.

Proposition

A strictly dominated action is a NWBR.

Proof

If action $a$$a$ is strictly dominated by an action $a^{\prime }$$a^\prime$, $u(a,b)<u(a^{\prime },b)$$u(a,b) < u(a^\prime,b)$, so $u_1(a,{\sigma }_2)<u_1(a^{\prime },{\sigma }_2)$$u_1(a,\sigma_2) < u_1(a^\prime , \sigma_2)$, so action $a$$a$ is a "Never a best response (NWBR)".

Mixed action

A mixed action for player 1 is a probability distribution ${\sigma }_1\in \mathrm{\Delta }(A_1)$$\sigma_1 \in \Delta(A_1)$,

The support of a mixed action is the set of pure actions given positive probability.

The expected utility (payoff) of ${\sigma }_1$$\sigma_1$ given beliefs ${\sigma }_2\in \mathrm{\Delta }(A_2)$$\sigma_2 \in \Delta(A_2)$ is

Suppose $a\in \text{Supp}({\sigma }_1)$$a \in \text{Supp}(\sigma_1)$ , and

This means that a mixed action cannot yield a payoff higher than the best pure action in its support, since the paoff of the mixture is a convex combination of payoff of the pure action in the support.

Solution concepts

• Equilibrium is in undominated strategies. We have already known that a rational player will not play a dominated action, sometimes this fact by itself is enough to give a prediction for the solution of the game

  Example

  

  Each player has only one action that is not strictly dominated , so $(D,D)$$(D,D)$ is the solution.

  Warning
  

  Solution is always a pair instead of a strategy

  Example - Sun rain game

  

  There is no strictly dominated action for player 1,

  $R$$R$ is strictly dominated by $S$$S$, so $S$$S$ is dominant. Player 2 will always plays $S$$S$.

  Then player 1 knows that Player 2 is rational and it will never play a strictly dominated action. Hence we can reduce the game by eliminating the strategy $R$$R$ for player 2.

  So $(NU,S)$$(NU,S)$ is the outcome for this game

   

  Notice that we obtain this solution by iteratively deleting the strictly dominated actions.

  Let's see what happens if we delete weakly dominated actions

  

  $T$$T$ strictly dominates $B$$B$, so we can eliminate the strategy $B$$B$ for player 1. P1 will never players $B$$B$.

  

  $(T,L)$$(T,L)$ and $(T,R)$$(T,R)$ can be the solution of the game

  But if we start with player 2 and eliminated the weak dominated strategy $R$$R$, then it will only result in one solution $(T,L)$$(T,L)$

  Warning
  

  Eliminating weakly dominated strategy could be risky of losing solutions, and the final solution depends on the orders of deleting. So we never eliminate weakly dominated strategies.

  Consider the following case

  P1\P2	D	E	F
  A	$(1,1)$$(1,1)$	$(1,1)$$(1,1)$	$(2,1)$$(2,1)$
  B	$(1,1)$$(1,1)$	$(0,0)$$(0,0)$	$(3,1)$$(3,1)$
  C	$(1,2)$$(1,2)$	$(1,3)$$(1,3)$	$(1,1)$$(1,1)$

  Starting P1

  $C$$C$ is weakly dominated by $A$$A$, $E$$E$ is weakly dominated by $F$$F$ , and $A$$A$ is also weakly dominated

  Then we have $(B,D)$$(B,D)$ and $(B,F)$$(B,F)$​ as the solution.

   

• Nash equlibrium

  A pure action profile $a^{\ast }=(a_1^{\ast },\dots ,a_N^{\ast })$$a^* = (a_1^*,\dots , a_N^*)$ is a Nash equilibrium if for each player $i$$i$,

  $$\begin{array}{}\text{(8)}& u_i(a_i^{\ast },a_{-i}^{\ast })\ge u_i(a_i,a_{-i}^{\ast })\text{ for every }{a}_i\in A_i\end{array}$$

  That is $a_i^{\ast }\in BR(a_{-i}^{\ast })$$a_i^* \in BR(a_{-i}^*)$ for every $i\in N$$i\in N$

  A mixed action profile ${\sigma }^{\ast }=({\sigma }_1^{\ast },\dots ,{\sigma }_N^{\ast })$$\sigma^* = (\sigma_1^*, \dots, \sigma_N^*)$ is a Nash equilibrium if for each player $i$$i$,

  $$\begin{array}{}\text{(9)}& BR({\sigma }^{\ast })\in BR({\sigma }_{-i}^{\ast })\end{array}$$

  That is $a_i\in BR({\sigma }_{-i}^{\ast })$$a_i \in BR(\sigma^*_{-i})$ for every $a_i\in \text{Supp}({\sigma }_i^{\ast })$$a_i \in \text{Supp}(\sigma_i^*)$.

  Example

  Prinsion Dilemma:

  

  Consider the best response,

  • for player 1, $D\in BR(D)$$D\in BR(D)$, and for player 2, $D\in BR(D)$$D\in BR(D)$.

    So $(D,D)$$(D,D)$ is a Nash equilibrium.

    We do not have a Minxed strategy nash equilibrium in this example, because strategy $C$$C$ is dominated by both agents, so $C$$C$ is a never a best response. So any mixed strategy that has positive probability on $C$$C$​ will be dominated as well and becomes a NWBR.

  Example - Sun rain game

  Consider this example again.

  

  • Player A $B{R}_1(S)=NU$$BR_1(S) = NU$, $B{R}_1(R)=U$$BR_1(R) = U$.

  • Player B $B{R}_2(NU)=S$$BR_2(NU) = S$, $B{R}_2(U)=S$$BR_2(U) = S$.

  • So the pure strategy nash equilibrium is $(NU,S)$$(NU,S)$ .

  Now, what about if we have this payoff?

  

  In this new payoff game, we have two pure strategy nash equilibrium $(NU,S)$$(NU,S)$ and $(U,S)$$(U,S)$.

  And we also have a mixed strategy nash equilibrium.

   

  Proposition

  Tip
  

  Any action played positive probability in any NE must survive iterated deletion of strictly dominated actions.

  Proof as homework

  Suppose there is an action that is played positive probability in a NE

   

  Looking for mixed action equilibrium

  Example - Battle of the sexes

  

  Two pure strategy nash equilibrium $(O,O)$$(O,O)$, and $(B,B)$$(B,B)$.

  Suppose the probability of your partner choosing $O$$O$ is ${\sigma }_2$$\sigma_2$, and your probability of playing $O$$O$ is ${\sigma }_1$$\sigma_1$​ .

  If you are mixing then you must be indifferent between $O$$O$ and $B$$B$​ which implies conditions on the action that your partner is playing

  So, for you, the expected util of playing $O$$O$ is $u_1(O,{\sigma }_2)=2{\sigma }_2$$u_1(O, \sigma_2) = 2\sigma_2$, and $u_1(B,{\sigma }_2)=1-{\sigma }_2,\Rightarrow {\sigma }_2=\frac{1}{3}$$u_1(B, \sigma_2) = 1-\sigma_2, \Rightarrow \sigma_2 = \frac13$.

  Similarly, your partner must be indifferent between $O$$O$ and $B$$B$ to be willing to mix.

  $u_2(O,{\sigma }_1)={\sigma }_1,u_2(B,{\sigma }_1)=2-2{\sigma }_1,\Rightarrow {\sigma }_1=\frac{2}{3}$$u_2(O,\sigma_1) = \sigma_1, u_2(B,\sigma_1) = 2-2\sigma_1, \Rightarrow \sigma_1 = \frac23$.

  Hence, $({\sigma }_1,{\sigma }_2)=(\frac{2}{3},\frac{1}{3})$$\left(\sigma_1,\sigma_2 \right) =\left(\frac23,\frac13\right)$ is the mixed strategy nash equilibrium in this example.

  ,Example - matching pennies

  

  This is a zero sum game:

  • $u_1(a,a^{\prime })+u_2(a,a^{\prime })=0$$u_1(a, a^\prime ) + u_2(a,a^\prime ) = 0$ for all $a\in A_1$$a\in A_1$ and $a^{\prime }\in A_2$$a^\prime \in A_2$.

  In this case, we do not have any best response to best responses. So we do not have any pure strategy nash equilibrium. But this does not imply that we cannot find any mixed strategy equlibrium, we need to check it.

  Suppose $({\sigma }_1,{\sigma }_2)$$(\sigma_1, \sigma_2)$ is a mixed action NE.

  Then, $E{u}_1(H)=2{\sigma }_2-1,E{u}_1(T)=1-2{\sigma }_2,\Rightarrow {\sigma }_2=0.5$$Eu_1(H) = 2\sigma_2-1, Eu_1(T) = 1-2\sigma_2, \Rightarrow \sigma_2 = 0.5$.

  Similarly, we can calculate ${\sigma }_1=0.5$$\sigma_1 = 0.5$.

  Therefore, we can find a mixed strategy nash equilibrium $({\sigma }_1,{\sigma }_2)=(0.5,0.5)$$(\sigma_1, \sigma_2) = \left(0.5,0.5\right)$.

  Tip
  

  Even if we cannot find a pure strategy nash equilibrium, it is possible to find a mixed strategy.

  Typically we will find an odd number of nash equilibriums.

  Example - Cournot duopoly

  There are two firms each of whom chooses a quantity. $q_i\in A_i={\mathbb{R}}^{+}$$q_i \in A_i = \R^+$. Let $Q=q_1+q_2$$Q = q_1 + q_2$,

  The payoffs are

  $$\begin{array}{}\text{(10)}& u_i(q_i,q_j)=q_{i}P(Q)-c_i(q_i)\end{array}$$

  $P(Q)$$P(Q)$ is the price of $Q$$Q$, which is inverse demand, and $c_i(q_i)$$c_i(q_i)$ is the cost of production.

  Let $P(Q)=a-Q$$P(Q) = a - Q$, $c_i=c(q_i)$$c_i = c(q_i)$, for each $i$$i$ and $a>c$$a>c$,

  The best response corresponces are

  $$\begin{array}{}\text{(11)}& BR(q_j)=\arg \underset{q_i}{max}{q}_i(a-q_i-q_j)-c{q}_i\end{array}$$

  Suppose there exists an interior solution,

  FOC:

  $$\begin{array}{}\text{(12)}& a-2q_i-q_j-c=0\end{array}$$

  Therefore,

  $$\begin{array}{}\text{(13)}& q_i(q_j)=\frac{a-q_j-c}{2}\text{ if }a-q_j-c>0\end{array}$$

  and $q_i(q_j)=0$$q_i(q_j) = 0$ otherwise.

  Then substitute it back to the b est response

  $$\begin{array}{}\text{(14)}& q_i^{\ast }=\frac{a-c-\frac{a-c-q_i^{\ast }}{2}}{2}\Rightarrow q_i^{\ast }=\frac{a-c}{3}\end{array}$$

  This is a simultaneously move game

  Question

  1. Suppose that a game has two NE. Suppose one of the NE involves weakly dominated actions and the other doesn't, which one is less likely to be played?

  2. Or suppose one of them is Pareto dominated by another NE. which one is less likely to be played?

  Let's have an example for illustration,

  	L	R
  T	$(10,0)$$(10,0)$	$(5,2)$$(5,2)$
  B	$(10,11)$$(10,11)$	$(2,11)$$(2,11)$

  The PSNEs are $(T,R)$$(T,R)$ and $(B,L)$$(B,L)$

  And we know that $(B,L)$$(B,L)$ pareto dominates $(T,R)$$(T,R)$.

  And if we see the both players' strategies, we know that $T$$T$ weakly dominates B, and $R$$R$ weakly dominates $L$$L$, so the $(B,L)$$(B,L)$​ is composed of weakly dominated actions.

  Then if we consider the 1st question, say maybe we choose $(T,R)$$(T,R)$, but if we consider the second question, we may choose $(B,L)$$(B,L)$, the answer becomes ambiguous.

  Tip
  

  Theorem

  Any finite game has at least one NE.

  Proof as homework

  Here is a short self-contained proof. We will define a function $\mathrm{\Phi }$$\Phi$ over the space of mixed strategy profiles. We will argue that that space is compact and that $\mathrm{\Phi }$$\Phi$ is continuous, hence the sequence define by: ${\sigma }^{(0)}$$\sigma^{(0)}$ arbitrary, ${\sigma }^{(n)}=\mathrm{\Phi }\left({\sigma }^{(n-1)}\right)$$\sigma^{(n)}=\Phi\left(\sigma^{(n-1)}\right)$, has an accumulation point. We will argue that every fixed point of $\mathrm{\Phi }$$\Phi$ must be a Nash equilibrium, hence the proof. The space of mixed strategy profiles is clearly compact, since it can be described as:

  $$\begin{array}{}\text{(15)}& \{\left({\alpha }_i^{\left(s_i\right)}\right):\mathrm{\forall }i,\sum _{s_i\in S_i}{\alpha }_i^{\left(s_i\right)}=1;\mathrm{\forall }i,\mathrm{\forall }{s}_i\in S_i,0\le {\alpha }_i^{\left(s_i\right)}\le 1\}\end{array}$$

  Given a mixed strategy profile $\alpha =\left({\alpha }_i^{\left(s_i\right)}\right)$$\alpha=\left(\alpha_i^{\left(s_i\right)}\right)$, the expected utility of player $i$$i$ is (extending the function $u_i$$u_i$ to mixed strategies)

  $$\begin{array}{}\text{(16)}& u_i(\alpha )=\sum _j\sum _{s_j\in S_j}{\alpha }_j^{\left(s_j\right)}{u}^i\left({\left(s_j\right)}_j\right).\end{array}$$

  The expected utility of player $i$$i$ if he were to play a particular pure strategy $s\in S_i$$s \in S_i$ instead of ${\left({\alpha }_i^{\left(s_i\right)}\right)}_{s_i}$$\left(\alpha_i^{\left(s_i\right)}\right)_{s_i}$ would be

  $$\begin{array}{}\text{(17)}& u_i(s,{\alpha }_{-i})=\sum _{j\ne i}\sum _{s_j\in S_j}{\alpha }_j^{\left(s_j\right)}{u}^i(s,{\left(s_j\right)}_{j\ne i}).\end{array}$$

  For $s\in S_i$$s \in S_i$, let $p_i(s,\alpha )=u_i(s,{\alpha }_{-i})-u_i(\alpha )$$p_i(s, \alpha)=u_i\left(s, \alpha_{-i}\right)-u_i(\alpha)$. The function $\mathrm{\Phi }$$\Phi$ will modify the mixed strategy of player $i$$i$ by shifting some of the weight of the distribution to give more weight to the set of strategies $s\in S_i$$s \in S_i$ for which $p_i(s)>0$$p_i(s)>0$, as follows: $\mathrm{\Phi }(\alpha )={\alpha }^{\prime }$$\Phi(\alpha)=\alpha^{\prime}$​, with

  $$\begin{array}{}\text{(18)}& {\alpha }_i^{\prime \left(s_i\right)}=\frac{{\alpha }_i^{\left(s_i\right)}+max(p_i(s_i,\alpha ),0)}{1+\sum _{s\in S_i}max(p_i(s,\alpha ),0)}\end{array}$$

  Clearly, $\mathrm{\Phi }$$\Phi$ is continuous. Finally, it is easy to see that

  $$\begin{array}{}\text{(19)}& \sum _{s:p_i(s,\alpha )>0}{\alpha }_i^{(s)}=\sum _{s:p_i(s,\alpha )>0}\frac{{\alpha }_i^{(s)}+p_i(s,\alpha )}{1+\sum _{s^{\prime }:p_i(s^{\prime },\alpha )>0}{p}_i(s^{\prime },\alpha )}\ge \sum _{s:p_i(s,\alpha )>0}{\alpha }_i^{(s)},\end{array}$$

  with equality achived only if $p_i(s,\alpha )\le 0$$p_i(s, \alpha) \leq 0$ for every $s$$s$. Every fixed point of $\mathrm{\Phi }$$\Phi$ must have $\sum _{s:p_i(s,\alpha )>0}{\alpha }_i^{\prime (s)}=\sum _{s:p_i(s,\alpha )>0}{\alpha }_i^{(s)}$$\sum_{s: p_i(s, \alpha)>0} \alpha_i^{\prime(s)}=\sum_{s: p_i(s, \alpha)>0} \alpha_i^{(s)}$ for every $i$$i$, hence must have $p_i(s,\alpha )\le 0$$p_i(s, \alpha) \leq 0$ for every $i$$i$ and every $s\in S_i$$s \in S_i$, hence must be a Nash equilibrium. This concludes the proof of the existence of a Nash equilibrium.

   

  JR Theorem 7.2 Proof

  Proof: Let $G={(S_i,u_i)}_{i=1}^N$$G=\left(S_i, u_i\right)_{i=1}^N$ be a finite strategic form game. To keep the notation simple, let us assume that each player has the same number of pure strategies, $n$$n$. Thus, for each player $i$$i$, we may index each of his pure strategies by one of the numbers 1 up to $n$$n$ and so we may write $S_i=\{1,2,\dots ,n\}$$S_i=\{1,2, \ldots, n\}$. Consequently, $u_i(j_1,j_2,\dots ,j_N)$$u_i\left(j_1, j_2, \ldots, j_N\right)$ denotes the payoff to player $i$$i$ when player 1 chooses pure strategy $j_1$$j_1$, player 2 chooses pure strategy $j_2,\dots$$j_2, \ldots$, and player $N$$N$ chooses pure strategy $j_N$$j_N$. Player $i$$i$ 's set of mixed strategies is $M_i=\{(m_{i1},\dots ,m_{in})\in {\mathbb{R}}_{+}^n\mid$$M_i=\left\{\left(m_{i 1}, \ldots, m_{i n}\right) \in \mathbb{R}_{+}^n \mid\right.$ $\sum _{j=1}^n{m}_{ij}=1\}$$\left.\sum_{j=1}^n m_{i j}=1\right\}$, where $m_{ij}$$m_{i j}$ denotes the probability assigned to player $i$$i$ 's $j$$j$ th pure strategy. Note that $M_i$$M_i$ is non-empty, compact, and convex.

  We shall show that a Nash equilibrium of $G$$G$ exists by demonstrating the existence of a fixed point of a function whose fixed points are necessarily equilibria of $G$$G$. Thus, the remainder of the proof consists of three steps: (1) construct the function, (2) prove that it has a fixed point, and (3) demonstrate that the fixed point is a Nash equilibrium of $G$$G$.

  Step 1: Define $f:M\to M$$f: M \rightarrow M$ as follows. For each $m\in M$$m \in M$, each player $i$$i$, and each of his pure strategies $j$$j$, let

  $$\begin{array}{}\text{(20)}& f_{ij}(m)=\frac{m_{ij}+max(0,u_i(j,m_{-i})-u_i(m))}{1+\sum _{j^{\prime }=1}^{n}max(0,u_i(j^{\prime },m_{-i})-u_i(m))}\end{array}$$

  Let $f_i(m)=(f_{i1}(m),\dots ,f_{in}(m)),i=1,\dots ,N$$f_i(m)=\left(f_{i 1}(m), \ldots, f_{i n}(m)\right), i=1, \ldots, N$, and let $f(m)=(f_1(m),\dots ,f_N(m))$$f(m)=\left(f_1(m), \ldots, f_N(m)\right)$. Note that for every player $i,\sum _{j=1}^n{f}_{ij}(m)=1$$i, \sum_{j=1}^n f_{i j}(m)=1$ and that $f_{ij}(m)\ge 0$$f_{i j}(m) \geq 0$ for every $j$$j$. Therefore, $f_i(m)\in$$f_i(m) \in$ $M_i$$M_i$ for every $i$$i$, and so $f(m)\in M$$f(m) \in M$.

  Step 2: Because the numerator defining $f_{ij}$$f_{i j}$ is continuous in $m$$m$, and the denominator is both continuous in $m$$m$ and bounded away from zero (indeed, it is never less than one), $f_{ij}$$f_{i j}$ is a continuous function of $m$$m$ for every $i$$i$ and $j$$j$. Consequently, $f$$f$ is a continuous function mapping the non-empty, compact, and convex set $M$$M$ into itself. We therefore may apply Brouwer's fixed-point theorem (Theorem A1.11) to conclude that $f$$f$ has a fixed point, $\hat{m}$$\hat{m}$.

  Step 3: Because $f(\hat{m})=\hat{m}$$f(\hat{m})=\hat{m}$, we have $f_{ij}(\hat{m})={\hat{m}}_{ij}$$f_{i j}(\hat{m})=\hat{m}_{i j}$ for all players $i$$i$ and pure strategies $j$$j$. Consequently, by the definition of $f_{ij}$$f_{i j}$,

  $$\begin{array}{}\text{(21)}& {\hat{m}}_{ij}=\frac{{\hat{m}}_{ij}+max(0,u_i(j,{\hat{m}}_{-i})-u_i(\hat{m}))}{1+\sum _{j^{\prime }=1}^{n}max(0,u_i(j^{\prime },{\hat{m}}_{-i})-u_i(\hat{m}))}\end{array}$$

  or

  $$\begin{array}{}\text{(22)}& {\hat{m}}_{ij}\sum _{j^{\prime }=1}^{n}max(0,u_i(j^{\prime },{\hat{m}}_{-i})-u_i(\hat{m}))=max(0,u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})).\end{array}$$

  Multiplying both sides of this equation by $u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})$$u_i\left(j, \hat{m}_{-i}\right)-u_i(\hat{m})$ and summing over $j$$j$ gives:

  $$\begin{array}{}\text{(23)}& \begin{array}{c}\sum _{j=1}^n{\hat{m}}_{ij}[u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})]\sum _{j^{\prime }=1}^{n}max(0,u_i(j^{\prime },{\hat{m}}_{-i})-u_i(\hat{m}))\\ =\sum _{j=1}^n[u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})]max(0,u_i(j,{\hat{m}}_{-i})-u_i(\hat{m}))\end{array}\end{array}$$

  Now, a close look at the left-hand side reveals that it is zero, because

  $$\begin{array}{}\text{(24)}& \begin{array}{rl}\sum _{j=1}^n{\hat{m}}_{ij}[u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})]& =\sum _{j=1}^n{\hat{m}}_{ij}{u}_i(j,{\hat{m}}_{-i})-u_i(\hat{m})\\ & =u_i(\hat{m})-u_i(\hat{m})\\ & =0\end{array}\end{array}$$

  where the first equality follows because the $m_{ij}$$m_{i j}$ 's sum to one over $j$$j$. Consequently, (P.1) may be rewritten

  $$\begin{array}{}\text{(25)}& 0=\sum _{j=1}^n[u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})]max(0,u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})).\end{array}$$

  But the sum on the right-hand side can be zero only if $u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})\le 0$$u_i\left(j, \hat{m}_{-i}\right)-u_i(\hat{m}) \leq 0$ for every $j$$j$. (If $u_i(j,{\hat{m}}_{-i})-u_i(\hat{m})>0$$u_i\left(j, \hat{m}_{-i}\right)-u_i(\hat{m})>0$ for some $j$$j$, then the $j$$j$ th term in the sum is strictly positive. Because no term in the sum is negative, this would render the entire sum strictly positive.) Hence, by part (c) of Theorem 7.1, $\hat{m}$$\hat{m}$ is a Nash equilibrium.

  Theorem 7.2 is quite remarkable. It says that no matter how many players are involved, as long as each possesses finitely many pure strategies there will be at least one Nash equilibrium. From a practical point of view, this means that the search for a Nash equilibrium will not be futile. More importantly, however, the theorem establishes that the notion of a Nash equilibrium is coherent in a deep way. If Nash equilibria rarely existed, this would indicate a fundamental inconsistency within the definition. That Nash equilibria always exist in finite games is one measure of the soundness of the idea.

   

•  

Extensive form games

Recall the battle of sexes game,

We know that the two PSNEs are $(O,O)$$(O,O)$ and $(B,B)$$(B,B)$. This is a simultaneous move game.

Suppose the man need decide first, then $(O,O)$$(O,O)$ will be played.

Integrents of extensive form game

• Players $0,1,\dots ,N$$0,1, \dots, N$ and Player $0$$0$ is nature. (Sometimes we use $N$$N$ to denote all individuals, the set of individuals)

• Nodes: $y\in Y=X\cup Z$$y\in Y = X \cup Z$

  • Decision nodes $x\in X$$x \in X$

  • Terminal nodes $z\in Z$$z \in Z$

• Directions

  predecessors and successors

  • Each node (except for initial node $x_0$$x_0$) has one immodiate predecessor.

  • Terminal nodes have no successor.

• The game tree is the initial node $x_0$$x_0$ and all its successors.

  • A subtree is any node and its successors

• Whose decision function

  $i:X\to N$$i: X \rightarrow N$​

  $i(x)$$i(x)$ is the player: who moves of decision node $x$$x$

• Actions: $A(x)$$A(x)$ is the set of actions available to player $i(x)$$i(x)$ at node $x$$x$.

  Each different act8ion leads to a different successor node.

   

Information sets

$H$$H$​ is a partition of decision node into information sets

A player cannot distinguish between nodes in an information set but can distinguish between information sets.

• $h(x)$$h(x)$ as the information set that contains decision node $x$$x$

• The same players at each decision node in an information set, if $x^{\prime }\in h(x),$$x^\prime \in h(x),$ then $i(x)=i(x^{\prime })$$i(x) = i(x^\prime )$

• The same actions are available at each decision node in an information set, i.e. if $x^{\prime }\in h(x)$$x^\prime \in h(x)$, then $A(x)=A(x^{\prime })$$A(x) = A(x^\prime)$​.

• Nature's moves: nature moves randomly according to commonly known probability

• Payoffs $u_i:\mathbb{Z}\to \mathbb{R}$$u_i: \Z \rightarrow \R$ ($\mathbb{Z}$$\Z$ is terminal nodes) that specify a player's utility payoff at each terminal node

Properties of extensive form game

• A game has perfected recall if players don't forget anything during the game

• A game has perfect information if each information set contains only one node: that is if playersknow the history of moves so far.

  For example in this game we have four information sets, three of them contains more than one nodes, so this game is not a perfect information game. It is simultaneously move game, which means any player does not know the other player's action.

  

• A game has complete information if the structure of the game is common knowledge (each player could draw the game tree).

• we will usually transform incomplete information games into imperfect information games by letting Nature choose the structure randomly and unobservably.

  Important
  

  Complete info and Perfect info

   

Strategies and payoffs

In extensive form game, we will distinguish strategies and actions. we don't do that for normal games.

Let $H_i=\{h\in H,i(h)=i\}$$H_i = \{h\in H, i(h) = i \}$ as the collection of information sets at which player $i$$i$ moves. Then the set of actions for player $i$$i$ is given by $A_i={\cup }_{h\in H_i}A(h)$$A_i = \cup_{h\in H_i}A(h)$​

The pure strategy for $i$$i$ is a function $s_i:H_i\to A_i$$s_i : H_i \rightarrow A_i$ s.t. $s_i(h)\in A(h)$$s_i(h) \in A(h)$ for all $h\in H_i$$h\in H_i$​

Let $S_i$$S_i$ denote the set of strategies for player $i$$i$, let $S=S_1\times S_2\times \cdots \times S_N$$S = S_1\times S_2 \times \dots \times S_N$.

A strategy is a complete contingent plan of actions.

A pure strategy specifies a player's choice of action of each of her information sets, even for sets that are not reached.

Then we define Mixed strategy ,

A mixed strategy $\sigma \in \mathrm{\Delta }(S_i)$$\sigma \in \Delta(S_i)$ fot player $i$$i$ is a probability distribution over pure strategies.

For example, $\{{\sigma }_1(Tt)={\sigma }_1(Tb)={\sigma }_1(Bt)=\frac{1}{3}\}$$\left\{\sigma_1 (Tt) = \sigma_1(Tb) = \sigma_1(Bt) = \frac13\right\}$

We know that we can transform extensive form game to normal form game by writting strategies and their corresponding payoffs. Then using this table we can calculate the mixed strategy nash equilibrium.

A Nash equilibrium of an extensive form game is a NE of the corresponding normal form game.

Refinement of NE

• Backward Induction

  is the process of analyzing a game from end to begin.

  Example

  A parent is driving Disneyland with a child in the back seat. The child is making a lot of noise. Parent says "be quiet, or I will turn this car around." This situation is represented in the following extensive form game, where the child's payoffs are given first.

  

  Write down the norm form game:

  	TT	TD	DT	DD
  Q	-10,-5	-10,-5	5,10	5,10
  N	-5,-10	10,5	-5,-10	10,5

  There are three pure strategy nash equilibrium here in the norm form game,

  $PSNE=\{(N,TD),(Q,DT),(N,DD)\}$$PSNE = \{(N,TD),(Q,DT), (N,DD)\}$.

  By back ward induction, the remaining strategy profile is $(N,DD)$$(N,DD)$​.

  The strategy profile $(Q,DT)$$(Q,DT)$ is a NE. But is th e parents actually willing to turn back at node $x_3$$x_3$(left lower node)? No

  So is that a credible threat? No

  Conditional on reaching node $x_3$$x_3$, Parent's BR is Disneyland. The same is true at node $x_2$$x_2$. Anticipating these decisions, child know that if he chooses quiet he will end up with payoff of 5 and if he choose noise he will end up with payoff of 10.

  The strategy profile $(N,DD)$$(N,DD)$ is the backward induction solution to this game and it's also a NE.

  Important
  

  Proposition

  Every backward induction solution of an extensive form game is NE.

  Every finite perfect information game has at least one backward induction solution in pure strategies. Thus every such game has a PSNE.

  But backward induction solutions may involve weakly dominated strategies.

  Example

  Consider this game:

  

  $S_1=\{A,B\}$$S_1 = \{A,B\}$, $S_2=\{C,D\}$$S_2 = \{C,D\}$.

  Consider the following normal form game:

  	C	D
  A	1,1	1,1
  B	1,1	0,0

  $(A,C)$$(A,C)$ and $(B,C)$$(B,C)$ are both solutions to this game, but $B$$B$ is weakly dominated.

  Example

  

  This is an imperction game, so backward induction cannot be applied. BUT we can still eliminate strategy $L$$L$ because it is strictly dominated.

  If we change the payoff to this scheme:

   

  We need subgame perfect

   

  Defination

  A subgame is a sub tree such that

  1. Starts at a decision node and

  2. Contains no broken information set

  That is if an information set contains a node in the subgame, then every node in that information set is contained in that subgame.

  Example:

  

  This game has 2 subgames. One starts from $x_1$$x_1$ and the other starts from $x_2$$x_2$​.

   

  Defination - SPNE

  A subgame perfect equilibrium is a profile of strategies where restrictions to any subgame forms a NE of that subgame.

  Note
  

  Every subgame perfect equilibrium is a NE (To the whole game), if a game has only one subgame, which is itself, then every NE is a subgame perfect Nash Equilibrium (SPNE).

  Tip
  

  In games of perfect information (we do not have any info set that contains multiple nodes, i.e. no simultaneous move game), the set of subgame perfect equilibria and the set of Backward induction are the same

  Our backward induction is actually deriving a SPNE.

  The advantage of subgame perfection is that it is defined even for games with imperfect information.

  TO find a SPNE in an imperfect information game, the procedure is similar to backward induction. we just replace subgames at the end of the game with their equilibrium payoffs, and repeat until you reach the initial node.

  Example

  

  There are two subgames in this game.

  For the second subgame, the normal form is,

  	P3	L	R
  Player 2
  T		0,1	1,0
  B		1,1	0,0

  $(B,L)$$(B,L)$ is the unique aNE of subgame strategies from $x_2$$x_2$.

  Then the payoff at node $x_2$$x_2$ degenerates to $(2,1,1)$$(2,1,1)$, then apply backward induction, palyer 1 will choose $D$$D$, and the SPNE is $(D,B,L)$$(D,B,L)$.

  Next, consider the following exercises: find all the Nash equilibriums in this game (Hint: rewrite this game into a normal form game, we typically need two matrixes)

  • When $U$$U$ is played by P1,

  • 	L	R
    T	1,10,10 ✅	1,10,10 ✅
    B	1,10,10	1,10,10 ✅

    When $D$$D$ is played by P1,

    	L	R
    T	0,0,1	0,1,0 😂
    B	2,1,1 ✅	0,0,0

  Example

  

  In this game, by backward induction, the SPNE is $(ddd,dd)$$(ddd,dd)$. but we do have other Nash equilibriums.

   

  Repeated Games

  Let's add a couple of actions to the battle of sexes.

  

  We have two pure strategy nash equilibriums.

  Now, let's augment some of the choices, adding $c_1$$c_1$ and $c_2$$c_2$.

  	O	B	C2
  O	2,1	0,0	6,0
  B	0,0	1,2	0,0
  C1	0,0	0,0	5,5

  Still, we have the same original two nash equilibrium. Adding $c_1$$c_1$ and $c_2$$c_2$ dpes not affect the set of NE, $(O,O)$$(O,O)$ and $(B,B)$$(B,B)$. It is sad that $(c_1,c_2)$$(c_1, c_2)$ is not equilibrium because then both players could get a payoff of $(5,5)$$(5,5)$. Unfortanotely player 1 would want to deviate to $O$$O$.

  But consider the game $G(2)$$G(2)$, where this game is played twice, First they play the game once, then both players actions are resolved to each other,and they play the game again.

  The payoffs from $G(2)$$G(2)$ are the sum of the payoffs in the two stages.

  There exists a SPNE in which $(c_1,c_2)$$(c_1, c_2)$ is played in stage 1. A pure strategy for player $i$$i$ is a pair of

  $$\begin{array}{}\text{(26)}& s_i^1\in \{O,B,c_i\}\end{array}$$

  , and in the second stage

  $$\begin{array}{}\text{(27)}& s_i^2\in \{O,B,c_1\}\times \{O,B,c_2\}\end{array}$$

  They represents your strategy in the first and second stage,

  The following strategy form a SPNE of $G(2)$$G(2)$

  $$\begin{array}{}\text{(28)}& \begin{array}{c}{s}_i^1=c_i\\ s_i^2=\{\begin{array}{l}O\text{ if }{a}_{-i}=c_{-i}\\ N\text{ o.w. }\end{array}\end{array}\end{array}$$

  We consider this repeated game using SPNE, in the second stage, the SPNE is $(O,O)$$(O,O)$ or $(B,B)$$(B,B)$. That is if man does not deviate from $c_1$$c_1$ in period 1 then he is rewarded with favoriate one stage equilibrium $(O,O)$$(O,O)$ in period 2, otherwise, $(B,B)$$(B,B)$​ is played.

  First, note that this strategy profile is a Nash equilibrium of the whole game. If man follow the equilibrium he gets payoff $5+2=7$$5+2 = 7$. If he deviates in the first period, he gets at most $6+1=7$$6+1 =7$, so deviating is not profitable. In the second round (stage), he has no incentive to deviate.

  For the woman, she does not has any incentive to deviate. She plays a statistic best response in both periods.

  The equilibrium is a SPNE because both $B,B$$B,B$ and $(O,O)$$(O,O)$ are NE of the second stage game.

   

  Now, lets define this game formally.

  Defination

  Given a normal form game $G$$G$ and $\delta \in [0,1]$$\delta \in [0,1]$, $G(T,\delta )$$G(T,\delta)$ is the repeated game with discount $\delta$$\delta$.

  A history $h^t=(a^1,a^2,\dots ,a^{t-1})$$h^t = (a^1, a^2,\dots, a^{t-1})$ is a list of the action profiles $a^s\in A$$a^s \in A$ played in each period $s<t$$s<t$. The history $h^t$$h^t$ is commonly known at the start of period $t$$t$. Let $H^t$$H^t$ denote the set of possible period $t$$t$​ histories.

  

  Like $h_1^2=(a_1)$$h_1^2 = (a_1)$, $a^1=(a_0,a_1)$$a^1 = (a_0,a_1)$.

  $h^3=(a^1)$$h^3 = (a^1)$

  $H^{T+1}$$H^{T+1}$ is the set of complete histories of the game which correspond to terminal nodes.

  A pure strategy for player 1 is $S_i=(s_i^1,\dots ,s_i^T)$$S_i = (s_{i}^1, \dots, s_i^T)$, where $S_i^t$$S^t_i$ where $S_i^t:H^t\to A_i$$S_i^t : H^t \rightarrow A_i$. After observing history $h^t$$h^t$, player $i$$i$ chooses action $s_i^t(h)\in A_i$$s^t_i(h) \in A_i$ The set of pure strategy for player $i$$i$ is $S_i$$S_i$ .

  The outcome of a pure strategy profile $S$$S$ is a history $h^{T+1}(S)$$h^{T+1}(S)$ defined recursively as $a^1=s^1(h^1)$$a^1 = s^1(h^1)$ and $a^1=s^1(h^1)$$a^1 = s^1(h^1)$ and $a^t=s^t(a^1,\dots ,a^{t-1})$$a^t = s^t(a^1, \dots, a^{t-1})$ for $2\le t\le T$$2\leq t\leq T$.

  Like the previous example,

  $a^2=s^2(a^1)$$a^2 = s^2(a^1)$,

  We define like $s_1^1(h^1)=a_1$$s^1_1(h^1) = a_1$, $s_2^1(h^1)=a_2\Rightarrow a^1=(a_1,a_2)\to h_2^2$$s_2^1(h^1) = a_2 \Rightarrow a^1 = (a_1, a_2) \rightarrow h_2^2$.

  Then we can also write in this way: $a_1^2=s_1^2(a^1)=s_1^2((a_1,a_2))=s_1^2(h_2^2)$$a_1^2 = s_1^2(a^1) = s_1^2((a_1, a_2)) = s_1^2(h^2_2)$.

  The value $\delta \in [0,1]$$\delta \in [0,1]$​ is the "discount factor". For simplicity, we will assume that is the some fof all players.

  Definations

  The payoff of player $i$$i$ from a complete history $h^{T+1}$$h^{T+1}$ is the sum of player $i$$i$​'s payoffs in each stage/period, Exponentially weighted by the discount factor.

  like, $h^{T+1}=(a^1,a^2,\dots ,a^T)$$h^{T+1} = (a^1, a^2, \dots, a^T)$

  ${\hat{u}}_i(h^{T+1})=u_i(a^1)+\delta u_i(a^2)+\cdots +{\delta }^{T-1}{u}_i(a^T)$$\hat u_i(h^{T+1}) = u_i(a^1) + \delta u_i(a^2) + \dots + \delta^{T-1} u_i(a^T)$.

  It will sometimes be convenient to rescale these payoffs so that they are directly comparable do the stage game payoff

  $$\begin{array}{}\text{(29)}& {\hat{u}}_i(h^{T+1})=\frac{1-\delta }{1-{\delta }^T}(u_i)\end{array}$$

  From now, we do not asuume $\delta =1$$\delta = 1$.

  If $T\to \mathrm{\infty }$$T \rightarrow \infin$, then, ${\hat{u}}_i(h^{\mathrm{\infty }})=(1-\delta )u_i$$\hat u_i(h^\infin) = (1-\delta) u_i$, and ${\hat{u}}_i(h^{\mathrm{\infty }})=(1-\delta )\sum _{t=1}^{\mathrm{\infty }}{\delta }^{t-1}{u}_i(a^t)$$\hat u_i (h^\infin) = (1-\delta) \sum_{t = 1}^\infin \delta^{t-1} u_i(a^t)$.

  if $h^{T+1}=(a,a,\dots ,a)$$h^{T+1} = \left(a,a,\dots, a\right)$.

  $$\begin{array}{}\text{(30)}& {\hat{u}}_i(h^{T+1})=\frac{1-\delta }{1-{\delta }^T}\sum _{t=1}^{T-1}{u}_i(a)=\frac{1-{\delta }^T}{1-\delta }c\end{array}$$

  say $u_i(a)=c$$u_i(a) = c$​

  ${\hat{u}}_i(h^{T+1})=u_i(a)???$$\hat u_i (h^{T+1}) = u_i(a)???$

  Tip
  

  Finitely repeated games

  Consider prisoner's dilemma. we repeat it for $T$$T$ times, $T<\mathrm{\infty }$$T<\infin$.

  	C	D
  C	-1,-1	-4,0
  D	0,-4	-3,-3

  There is a unique NE for stage game.

  Here becasue each subgame only have one nash equilibrium, so when we do backward induction, we can degenerate the game tree always with a certain equilibrium. So there will be no room for punishment to deviate from the nash equilibrium at each stage.

  Formally, we say in any subgame perfect equilibrium of $G(T,\delta )$$G(T,\delta)$, $(D,D)$$(D,D)$ must be played in period $T$$T$. That means that what happens in the second-to-last period cannot affect play in the last period. So players must choose static best response in period $T-1$$T-1$, which means an equilibrium of stage game, that is $(D,D)$$(D,D)$ will be played. Similarly $(D,D)$$(D,D)$ will be played in every period.

  Proposition

  Suppose that stage game $G$$G$ has a unique NE $a^{\ast }$$a^*$ and $T<\mathrm{\infty }$$T<\infin$, Them, the only SPNE of $G(T,\delta )$$G(T,\delta)$ is to play $a^{\ast }$$a^*$ in every period.

  if the stage game has more than one NE, then the finitely repeated game has more than one subgame perfect equilibrium. For example, for each $t$$t$​, we could specify a subgame equilibrium to be played in that period regardless of history

  ---

   

  Given a normal form game, let $a_{-i}$$a_{-i}$ be the mixed action profile for all players other than player $i$$i$. Let $w_i({\alpha }_{-i})=max{u}_i(a_i,a_{-i})$$w_i(\alpha_{-i}) = \max u_i(a_i,a_{-i})$, is $i$$i$'s payoff from best responding to ${\alpha }_{-i}$$\alpha_{-i}$.

  The minmax payoff ${\nu }_i$$\nu_i$ for $i$$i$​ is

  $$\begin{array}{}\text{(31)}& {\nu }_i=\underset{{\alpha }_{-i}}{min}{w}_i({\alpha }_{-i})=\underset{{\alpha }_{-i}}{min}\underset{{\alpha }_i}{max}{u}_i(a_i,a_{-i})\end{array}$$

  That is the other players are minimizing the value of $i$$i$'s maximum payoff. when he best responds.

  The minmax strategy that they (the other players) use against $i$$i$ is

  $$\begin{array}{}\text{(32)}& m_i=\underset{{\alpha }_{-i}}{\mathrm{argmin}}{w}_i\left({\alpha }_{-i}\right)\end{array}$$

  Proposition

  For any $T$$T$ and $\delta$$\delta$, player $i$$i$'s payoff in NE of $G(T,\delta )$$G(T,\delta)$ is at least ${\nu }_i$$\nu_i$.

  Note
  

  Proof idea

  Player $i$$i$ can guarantee herself no less than ${\nu }_i$$\nu_i$ by playing a static best response in every periods. Thus she has a profitable deviation from any strategy profile that gives her a lower payoff than ${\nu }_i$$\nu_i$

  Tip
  

  Example

  

  Since $C$$C$ weakly dominates $D$$D$, So to minmax player 2, player 1 choose the action $A$$A$ that minimizizes player 2's payoff from playing $C$$C$, ${\nu }_2=\underset{A,B}{min}\{1,3\}=1$$\nu_2 = \min_{A,B} \{1,3\} = 1$, and $m_2=A$$m_2 = A$

  For ${\nu }_1$$\nu_1$: Note that player 1's lowest payoff when player 2 plays $C$$C$ is greater than his highest payoff when player 2 plays $D$$D$. So minmax player 1, player 2 chooses $D$$D$. So ${\nu }_1=0$$\nu_1 = 0$, $m_1=D$$m_1 = D$ .

  Tip
  

  Example

  

  Think about the mixed strategy.

  To find $m_1$$m_1$ and ${\nu }_1$$\nu_1$, observe that if player 2 chooses $H$$H$ with probability $p$$p$ then $w_1(p)=max\{2p-1,1-2p\}$$w_1(p) = \max \{2p-1, 1-2p\}$. $p\in [0,1]$$p \in [0,1]$.

  • if $p\ne 0.5$$p\neq 0.5$, then $w_1(p)>0$$w_1(p) > 0$

  • $p<0.5$$p<0.5$, $1-2p>0$$1-2p>0$

  • $p>0.5$$p>0.5$, $2p-1>0$$2p-1>0$.

  • which means that $m_1={\sigma }_2(H)=0.5$$m_1 = \sigma_2(H) = 0.5$, and ${\nu }_1=0$$\nu_1 = 0$​

  • $m_2={\sigma }_1(H)=0.5$$m_2 = \sigma_1(H) = 0.5$, and ${\nu }_2=0$$\nu_2 = 0$.

  Infinitely Repeated Games

  The principle of optimality (also known as the one shot deviation principle) is most useful when we deal with in finitely repeated games Principle of optimality

  A strategy profile $\sigma$$\sigma$ is a SPNE iff no player at any history (on or off the equilibrium path) can improve her payoffs from that point by deviating from $\sigma$$\sigma$ exactly one time (at that history) and playing $\sigma$$\sigma$​ again afterwards.

  The principle of optimality makes checking for subgame perfection much easier by reducing the number of deviations that we need to check. The idea is that if there is any profitable deviation, then there must be profitable one-shot deviation.

  Tip
  

  Example

  

  Strategy:

  $S_i^{\prime }=C_i$$S_i^{\prime}=C_i$ and for $\begin{array}{c}t>1s_i^t\left(h^t\right)=\{\begin{array}{ll}{c}_i& \text{ if }{a}_1^s=C_1,\text{and }{a}_2^s=C_2\\ N.& \text{ otherwise }\end{array}\end{array}$$t>1 \quad s_i^t\left(h^t\right)= \begin{cases}c_i & \text { if } a_1^s=C_1, \text{and } a_2^s = C_2 \\ N . & \text { otherwise }\end{cases}$​

  $(C_1,C_2)$$(C_1,C_2)$ is played in every period until someone deviates and then $(N,N)$$(N,N)$​ is played forever. There ore two types of histories that we need to check: those when no one has deviated and those after a deviation

  if no one has deviated, Man's equilibrium continuation payoff is $5+\delta 5+{\delta }^{2}5+\cdots =\frac{5}{1-\delta }$$5+ \delta 5+\delta^2 5+\dots = \frac{5}{1-\delta}$.

  Since any deviation results in the same future play, Man's best deviation is his best static deviation is $J$$J$.

  Then the payoff is $6+\delta +{\delta }^2+\cdots =6+\frac{\delta }{1-\delta }$$6 + \delta + \delta^2 +\dots = 6 + \frac{\delta}{1-\delta}$​.

  Then we look at the woman's equilibrium continution, woman's best deviation is either $N$$N$ or $J$$J$, both yield continuation payoff of $0+\frac{2\delta }{1-\delta }$$0+ \frac{2\delta}{1-\delta}$.

  In any history after a deviation, man's equilibrium continuation payoff is $\frac{1}{1-\delta }$$\frac{1}{1-\delta}$​. Now any further deviation does not affect future play so again man's best deviation is his best static deviation.

  Refinement of SPNE

  

  In this game we have two SPNE, pure strategy, $(T,R)$$(T,R)$ and $(B,L)$$(B,L)$.

  But for player 2, $L$$L$ is always better than $R$$R$ in payoffs. No belief that player 2 can have about which node she is at in her info set one consistent with $R$$R$ giving higher expected utility payoff than $L$$L$​. The action/strategy is conditionally strictly dominated.

  So, even if $(T,R)$$(T,R)$ is SPNE, no belief that we will play at there.

  We ought to require that at nontrival info sets, players maximized expected utility according to some beliefs about which node they are at.

  Tip
  

  Example

  

  There are two subgames.

  

  We know that $(Du,a,L)$$(Du,a,L)$ is the SPNE, player 2 is not bestresponding to player 3's strategy. The best response for player 2 in that case is playing $b$$b$

   

  Perfect Bayesian Equilibrium

  Let decision node $x$$x$ be an element of Player $i$$i$'s information set $h$$h$, Then ${\mu }_i(x\mid h)$$\mu_i(x\mid h)$ is player $i$$i$'s conditional belief that she is at node $x$$x$ given that she is of some node in $h$$h$​

  Tip
  

  Understanding in this way:

  

  $$\begin{array}{}\text{(33)}& \begin{array}{rl}& \mathrm{Pr}(h)=\mathrm{Pr}\left(x_1\right)+\mathrm{Pr}\left(x_2\right)\\ & \mathrm{Pr}(x_1\mid h)=\frac{\mathrm{Pr}\left(x_1\right)}{\mathrm{Pr}(h)}=\frac{\mathrm{Pr}\left(x_1\right)}{\mathrm{Pr}\left(x_1\right)+\mathrm{Pr}\left(x_2\right)}\\ & \mathrm{Pr}(x_1\mid h)+\mathrm{Pr}(x_2\mid h)=1\end{array}\end{array}$$

  In our analysis, we allow nature to be the the first player in the games in which we have nature. Given the strategy profile $\sigma (\text{including nature’s moves})$$\sigma(\text{including nature's moves})$ Bayes rule pins down conditional belief at info sets that are reached with positive probability.

  Defination

  [Blelief] An assesment is strategy/condtional belief pair $(\sigma ,\mu )$$(\sigma, \mu)$ where the function $\mu :X\to [0,1]$$\mu: X \rightarrow [0,1]$​, gives conditional beliefs of each information set including the trivial ones.

  Note
  

  A system of beliefs $\mu$$\mu$ in extensive form game ${\mathrm{\Gamma }}_E$$\Gamma_E$ is a specification of a probability $\mu (x)\in [0,1]$$\mu(x) \in[0,1]$ for each decision node $x$$x$ in ${\mathrm{\Gamma }}_E$$\Gamma_E$ such that $\sum _{x\in H}\mu (x)=1$$\sum_{x \in H} \mu(x)=1$ for all information sets $H$$H$.

  • A system of beliefs specify, for each information set, a probabilistic assessment by the player who moves there, conditional upon play having reached that information set.

  • Let $E[u_i\mid H,\mu ,{\sigma }_i,{\sigma }_{-i}]$$E\left[u_i \mid H, \mu, \sigma_i, \sigma_{-i}\right]$ be Player i's expected utility starting at $H$$H$ if she has beliefs $\mu$$\mu$ and follows strategy ${\sigma }_i$$\sigma_i$ and other players use ${\sigma }_{-i}$$\sigma_{-i}$.

  [Sequentially rational] An assessment $(\sigma ,\nu )$$(\sigma, \nu)$ is "sequentially rational" if playing ${\sigma }_i$$\sigma_i$ maximizes expected utility given $\mu$$\mu$ for each player $i$$i$ at each of player $i$$i$'s information sets

  That is $\sigma$$\sigma$ is a BR for all player given $\mu$$\mu$​

  Note
  

  A formal statement

  A strategy profile $\sigma$$\sigma$ in extensive form game ${\mathrm{\Gamma }}_E$$\Gamma_E$ is sequentially rational at information set $H$$H$ given a system of beliefs $\mu$$\mu$ if, denoting by $\iota (H)$$\iota(H)$ the player who moves at $H$$H$, we have

  $$\begin{array}{}\text{(34)}& E[u_{\iota (H)}\mid H,\mu ,{\sigma }_{\iota (H)},{\sigma }_{-\iota (H)}]\ge E[u_{\iota (H)}\mid H,\mu ,{\tilde{\sigma }}_{\iota (H)},{\sigma }_{-\iota (H)}]\end{array}$$

  for all ${\tilde{\sigma }}_{\iota (H)}\in \mathrm{\Delta }\left(S_{\iota (H)}\right)$$\tilde{\sigma}_{\iota(H)} \in \Delta\left(S_{\iota(H)}\right)$. If strategy profile $\sigma$$\sigma$ satisfies this condition for all information sets $H$$H$, then we say that $\sigma$$\sigma$ is sequentially rational given belief system.

  An assessment $(\sigma ,\mu )$$(\sigma, \mu)$ is a Perfect Bayesian equilibrium ((PBE)), if

  • it is sequential rational , and

  • belief $\mu$$\mu$ one given by Bayes's rule applied to Nature's move and to $\sigma$$\sigma$​ "Whenever possible"

  Note
  

  Proposition

  if $(\sigma ,\mu )$$(\sigma, \mu)$ is a PBE, then $\sigma$$\sigma$​​​ is SPNE,

  Proof by intuition

  Suppose $\sigma$$\sigma$ is not a SPNE, then by defination, $\sigma$$\sigma$ is not always the Nash equilibrium in every subgames. Therefore, for each player, there could be other possible strategies ${\sigma }^{\prime }$$\sigma^\prime$ at each decision nodes that could give higher payoffs. In other words, given some information set $H$$H$, $\sigma$$\sigma$ is not the NE of the subgame given $H$$H$.

  Therefore, denoting by $\iota (H)$$\iota(H)$ the player who moves at $H$$H$, given other players' strategies, we have $u_{\iota (H)}({\sigma }^{\prime })>u_{\iota (H)}(\sigma )$$u_{\iota(H)}(\sigma^\prime) > u_{\iota(H)}(\sigma)$.

  Hence, given belief $\mu$$\mu$, we have

  $$\begin{array}{}\text{(35)}& E[u_{\iota (H)}\mid H,\mu ,{\sigma }_{\iota (H)}^{\prime },{\sigma }_{-\iota (H)}]\ge E[u_{\iota (H)}\mid H,\mu ,{\sigma }_{\iota (H)},{\sigma }_{-\iota (H)}]\end{array}$$

  This inequality condition violates the defination of sequential rationality. So in that case, if $\sigma$$\sigma$ is not a SPNE, then $(\sigma ,\mu )$$(\sigma,\mu)$ cannot be the PBE.

  Therefore, if $(\sigma ,\mu )$$(\sigma, \mu)$ is a PBE, then $\sigma$$\sigma$ is SPNE.

   

  Tip
  

  Example

  

  In order to find PBE, we know it must be a subset of SPNE, so we can first find the set of SPNE.

  In this example, we only find one SPNE, so it must be part of PBE.

  And suppose player 2 know that player 1 will always choose $D$$D$, and player 3 knows player 2 will always choose $B$$B$, so player 3's belief is updated.

  When $(D,B,R)$$(D,B,R)$ is played, every info set is reached. So beliefs are given by Bayes rule ${\mu }_3(x_3\mid h)=0$$\mu_3(x_3\mid h) = 0$, ${\mu }_3(x_4\mid h)=1$$\mu_3(x_4\mid h) = 1$​

  Another example,

  

  we know that in this game $(T,R)$$(T,R)$, and $(B,L)$$(B,L)$ are the SPNE,

  We know that $(T,R)$$(T,R)$ is not a part of PBE, why?

  if $B$$B$ is played, then ${\mu }_3(x_3\mid h)=1$$\mu_3(x_3 \mid h) = 1$.

  $$\begin{array}{}\text{(36)}& ((B,L),{\mu }_2(x_2\mid h)=0)\to PBE\end{array}$$

  Tip
  

  Example

  

  In this game, player 2 only knows the player 1 chooses $In$$In$ or $Out$$Out$, but do not know exactly whether nature choose $L$$L$ or $R$$R$.

  We only have one subgame,

  

  Each of the part, $L,R$$L,R$ has the probability of $0.5$$0.5$. so the expected utility is then,

  

  The NE of this game is $(Out,a)$$(Out, a)$, $(In,b)$$(In, b)$

  They are SPE,

  $\mu (x_1=0.5),\mu (x_3=0.5)$$\mu(x_1 = 0.5), \mu(x_3 = 0.5)$​

  Then,,

  $$\begin{array}{}\text{(37)}& ((In,b),\mu (x_1)=0.5,\mu (x_3)=0.5)\to PBE\end{array}$$

  Homework